Search for: All records

A promising avenue for the preparation of Gibbs states on a quantum computer is to simulate the physical thermalization process. The Davies generator describes the dynamics of an open quantum system that is in contact with a heat bath. Crucially, it does not require simulation of the heat bath itself, only the system we hope to thermalize. Using the state-of-the-art techniques for quantum simulation of the Lindblad equation, we devise a technique for the preparation of Gibbs states via thermalization as specified by the Davies generator.In doing so, we encounter a severe technical challenge: implementation of the Davies generator demands the ability to estimate the energy of the system unambiguously. That is, each energy of the system must be deterministically mapped to a unique estimate. Previous work showed that this is only possible if the system satisfies an unphysical 'rounding promise' assumption. We solve this problem by engineering a random ensemble of rounding promises that simultaneously solves three problems: First, each rounding promise admits preparation of a 'promised' thermal state via a Davies generator. Second, these Davies generators have a similar mixing time as the ideal Davies generator. Third, the average of these promised thermal states approximates the ideal thermal state.

 

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of ann-dimensional convex body within multiplicative error ε usingÕ(n³+ n^2.5/ε) queries to a membership oracle andÕ(n⁵+n^4.5/ε)additional arithmetic operations. For comparison, the best known classical algorithm usesÕ(n^3.5+n³/ε²)queries andÕ(n^5.5+n⁵/ε²)additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requiresΩ (√ n+1/ε)quantum membership queries, which rules out the possibility of exponential quantum speedup innand shows optimality of our algorithm in 1/ε up to poly-logarithmic factors.

 

We present an efficient quantum algorithm for simulating the dynamics of Markovian open quantum systems. The performance of our algorithm is similar to the previous state-of-the-art quantum algorithm, i.e., it scales linearly in evolution time and poly-logarithmically in inverse precision. However, our algorithm is conceptually cleaner, and it only uses simple quantum primitives without compressed encoding. Our approach is based on a novel mathematical treatment of the evolution map, which involves a higher-order series expansion based on Duhamel’s principle and approximating multiple integrals using scaled Gaussian quadrature. Our method easily generalizes to simulating quantum dynamics with time-dependent Lindbladians. Furthermore, our method of approximating multiple integrals using scaled Gaussian quadrature could potentially be used to produce a more efficient approximation of time-ordered integrals, and therefore can simplify existing quantum algorithms for simulating time-dependent Hamiltonians based on a truncated Dyson series. 

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ²-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

 

Purpose To develop a method of biologically guided deep learning for post-radiation 18 FDG-PET image outcome prediction based on pre-radiation images and radiotherapy dose information. Methods Based on the classic reaction–diffusion mechanism, a novel biological model was proposed using a partial differential equation that incorporates spatial radiation dose distribution as a patient-specific treatment information variable. A 7-layer encoder–decoder-based convolutional neural network (CNN) was designed and trained to learn the proposed biological model. As such, the model could generate post-radiation 18 FDG-PET image outcome predictions with breakdown biological components for enhanced explainability. The proposed method was developed using 64 oropharyngeal patients with paired 18 FDG-PET studies before and after 20-Gy delivery (2 Gy/day fraction) by intensity-modulated radiotherapy (IMRT). In a two-branch deep learning execution, the proposed CNN learns specific terms in the biological model from paired 18 FDG-PET images and spatial dose distribution in one branch, and the biological model generates post-20-Gy 18 FDG-PET image prediction in the other branch. As in 2D execution, 718/233/230 axial slices from 38/13/13 patients were used for training/validation/independent test. The prediction image results in test cases were compared with the ground-truth results quantitatively. Results The proposed method successfully generated post-20-Gy 18 FDG-PET image outcome prediction with breakdown illustrations of biological model components. Standardized uptake value (SUV) mean values in 18 FDG high-uptake regions of predicted images (2.45 ± 0.25) were similar to ground-truth results (2.51 ± 0.33). In 2D-based Gamma analysis, the median/mean Gamma Index (<1) passing rate of test images was 96.5%/92.8% using the 5%/5 mm criterion; such result was improved to 99.9%/99.6% when 10%/10 mm was adopted. Conclusion The developed biologically guided deep learning method achieved post-20-Gy 18 FDG-PET image outcome predictions in good agreement with ground-truth results. With the breakdown biological modeling components, the outcome image predictions could be used in adaptive radiotherapy decision-making to optimize personalized plans for the best outcome in the future. 

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix, sublinear algorithms for the matrix game were previously known only for two special cases: (1) the maximizing vectors live in the L1-norm unit ball, and (2) the minimizing vectors live in either the L1- or the L2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q between 1 and 2, we solve, within some additive error, matrix games where the minimizing vectors are in an Lq-norm unit ball. We also provide a corresponding sublinear quantum algorithm that solves the same task with a quadratic improvement in dimensions of the maximizing and minimizing vectors. Both our classical and quantum algorithms are optimal in the dimension parameters up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the Lq-margin support vector machines as applications.